package com.ztom.offer.v2;

/**
 * 二叉搜索树与双向链表
 * <p>
 * https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 *
 * @author ZhangTao
 */
public class Code36TreeToDoublyList {

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        dfs(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

    private void dfs(Node node) {
        if (node == null) {
            return;
        }

        // 中序
        dfs(node.left);

        if (pre == null) {
            // 初始化 head
            head = node;
        } else {
            pre.right = node;
        }
        node.left = pre;
        pre = node;

        dfs(node.right);
    }
}
